package LC;

import java.util.HashSet;

/**
 * https://leetcode.com/problems/longest-consecutive-sequence/description/
 * Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
 * For example,
 * Given [100, 4, 200, 1, 3, 2],
 * The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
 * Your algorithm should run in O(n) complexity.
 */
public class LC_128_LongestConsecutiveSequence_Loop_HashSet {
    public static void main(String[] args) {
        int maxLen = Solution.longestConsecutive(new int[]{-1, 0, 1, 2, 3, 100});
        System.out.println(maxLen);
    }

    static class Solution {
        static int longestConsecutive(int[] num) {
            if (num == null || num.length == 0) return 0;
            HashSet<Integer> hs = new HashSet<>();
            for (int aNum : num) hs.add(aNum);
            int max = 0;
            for (int aNum : num) {
                if (hs.contains(aNum)) {
                    int count = 1;
                    hs.remove(aNum);
                    int low = aNum - 1;
                    while (hs.contains(low)) {
                        hs.remove(low);
                        low--;
                        count++;
                    }
                    int high = aNum + 1;
                    while (hs.contains(high)) {
                        hs.remove(high);
                        high++;
                        count++;
                    }
                    max = Math.max(max, count);
                }
            }
            return max;
        }
    }
}
